This invention relates to a computer system for inspecting objects for manufacturing defects and more particularly to an algorithm in the computer system for inspecting and analyzing periodic arrays of electronically acquired imagery of an object.
While advances in computer processing power have made processing of large amounts of data possible, an automated optical inspection problem for arrays of geometric targets still exists. Automated optical inspection is the inspection of electronically acquired imagery of an object for tolerance, color, blemishes, cracks or a wide variety of manufacturing defects that might be present in the object. The automated optical inspection problem arises, among other places, in the inspection of aperture masks used in CRT-type color monitors and television sets. Problems encountered during aperture masks inspections also occur during inspections of other objects, which include inspection of periodic arrays of annular targets. Thus, two seemly different objects, such as flat panel displays and filters for filtering bacterial particles out of a product stream of bio-engineered vaccines and chemicals have the same inspection problem. Therefore, while the following discusses inspection of aperture masks with arrays of annular targets, it should be apparent to one of ordinary skill in the art that the invention relates to inspection of all objects with arrays of geometric targets.
Aperture masks generally are comprised of thin metal sheets perforated by hundreds of thousands of tiny holes. These holes are too small to see with an unaided eye and each hole has a precise shape, or profile. The shape of each hole varies slightly and definitely according to its position across the width and/or height of the mask. The degree to which the shape of these holes can be maintained in manufacturing of the aperture mask has a direct bearing on whether the mask can be used by a manufacturer.
Inspection of aperture masks during manufacturing is a particularly demanding problem because there are vast numbers of holes, at least several hundred thousand holes, in each mask. Aperture masks are relatively inexpensive to manufacture. Nonetheless, the shape of a single hole that is out of tolerance eventually shows up as a blemish that an end user can see in a finished product. For example, the end user will see a blemish in an image that is produced by a CRT-type color monitor, which includes the defective aperture mask. Thus, automated or manual inspection of each mask has to be performed. Automated inspection by a computer leads to a formidable data reduction problem since each hole must be covered by many pixels, thereby producing billions of pixels across the length and width of each mask.
Some manufacturers use human inspectors to manually inspect each mask but do not use any special magnification method. The human inspectors hold each mask up to the light and bend it in various ways to detect an irregular hole or area in the mask. While the manufacturing of the aperture masks is automated, inspections of the masks are performed by groups of inspectors. Each person in a group may inspect a particular section of the masks and inspections of the masks are performed at much slower rates than the rates at which the masks are manufactured. The manual inspection process also is a relatively expensive undertaking for the manufacturer.
A current automated method uses two-dimensional video cameras to analyze data on a computer. Thereafter various mathematical operations, such as edge detection, a gradient calculation, or some other type of transform to manipulate the data, are performed on the two-dimensional representation of the data. The automated method measures the inside and outside diameter of each hole to calculate whether the inner diameter is the right range of tolerance. This method generates an unusable and impractical amount of data that may only be analyzed by a very specialized and expensive computer. In an industrial environment, the masks vibrate as they emerge from the production line. This vibration is enough to make an image useless unless the image is taken over an extremely short time period.
U.S. patent application Ser. No. 09/522,685 of which this application is a continuation-in-part, relates to a system and method for inspecting electronically acquired imagery, from a one-dimensional camera, of an object for tolerance, color, blemishes, cracks or a wide variety of manufacturing defects that might be present in an object. The method to detect manufacturing defects includes an algorithm for analyzing the periodic pattern of geometric elements in an array and detecting deviations from numerical acceptance norms, such as diameter, spacing, and symmetry, for the geometric elements.
This previously filed application, moreover, discloses a method for analyzing one-dimensional image data. The process of analyzing two-dimensional images, however, is useful in fields of failure analysis and prediction, process control, machine vision and automated optical inspection, and voice recognition (especially in the presence of xe2x80x9cnoisexe2x80x9d, data compression, vibration control and echo suppression). What is needed, therefore, is an automated algorithm for inspecting imagery of any one or two-dimensional object that can be implemented by means for parallel hardware scales at a favorable rate with limited inter-processor communication. The method must also be unaffected by the visual effects of mechanical vibration on an image while tolerating the effects of imperfect positions of the target object by an operator or as a result of equipment shortcomings.
The present invention relates to a system and method for scanning electronically acquired periodic images from an object and thereafter, inspecting the periodic images by using predetermined rules. The method to inspect the image includes an algorithm for analyzing the periodic patterns of the image and detecting deviations from numerical acceptance norms. In the system, the field of view of a camera, such as a video camera, viewing the object includes a two-dimensional image of the object. The camera captures the two-dimensional image of the object and converts the image into an array of scan lines, whereby each scan line represents a one-dimensional xe2x80x9cslicexe2x80x9d of target shape of the object. Hence, while all two dimensional images do not have periodic patterns, the array of scan lines represent a periodic pattern that is used by the algorithm in the inventive system. Alternatively, the camera may capture a scan line of a one-dimensional image with periodic elements, whereby the scan line represents a one-dimensional slice of target shape.
Each slice is broken down into xe2x80x9csegmentsxe2x80x9d consisting of sets of adjacent pixels that are similar in brightness, hue, or both. The camera, in conjunction with processing by ancillary electronic data processing means and methods, delivers the slices with segments to the system where they are sequenced. The system identifies every slice and segment to determine what feature of the target shape the slice and segment represent. Thereafter, predefined rules are used to determine if each identified segment deviates from numerical acceptance norms. The method is thus used to analyze periodic elements of any arbitrary target shape, thereby working in a range of different object acceptance norms and being easily adaptable to change from one set of norms to another.
The algorithm used in the inventive method accomplishes at least two outcomes simultaneously. It serves as a framework for the transformation of a set of measurements that could be made on a two-dimensional image of the target area into a set of measurements made only on the one-dimensional data set. In addition, the algorithm is capable of accurately measuring a lattice constant, i.e., the spacing between the geometric elements of an array that arises from a data set only after certain manipulations have been made. The lattice constant can be measured without prior knowledge of any scan line other than the one currently being observed. Thus, it is never necessary to assemble a two-dimensional depiction of the one-dimensional video data. This is important in a design of computational hardware to analyze the video data stream generated by any camera, such as a one-dimensional camera or a two-dimensional camera.
Specifically, in a preferred embodiment, the algorithm is used to inspect any array of periodic elements. The inventive method uses predefined rules, whereby not all possibilities in the analysis work. For example, rules may include a pattern rule, derived from the geometry of the scanned elements, a lattice constant rule for estimating the spacing between periodic elements of an array, and an inference rule for analyzing a two-dimensional image. It should be noted that other rules may be used in inspecting and analyzing arrays of periodic elements.
For two-dimensional images, the video camera captures an image of the object and converts the captured image into an array of one-dimensional scan lines of target shape of an object. For one-dimensional images, the video camera captures a single one-dimensional scan line of target shape of an object. First, each scan line data is reduced to a collection of numbers, each representing the brightness of a particular pixel, to xe2x80x9crun-length encodedxe2x80x9d data. In an embodiment of the invention, the system reduces the scan line data to black and white images by determining if the data is darker or brighter than a predefined threshold. Thus, each pixel in the scan line is reduced to a single bit in the system. As would be apparent to one of ordinary skill in the art, there are other ways of reducing the data to binary data. A consecutive set of all dark or white pixels in a scan line is thus defined as a run. In an alternate embodiment, the system works on data represented in non-binary formats. For example, the system will work with multi-color data encrypted by three or more bits or with analog data in a numeric form.
In a preferred embodiment, the system thereafter generates a set of run-length integers from the reduction of the scan line data. The algorithm implemented in the inventive method applies a technique of search to analyze run-length data derived from each scan line data. Using predefined rules, the system systematically accounts for every possible interpretation of each of the run-length integers, whereby each interpretation is systematically tested using the above mentioned rules and those interpretations that cannot be valid are ignored. When an interpretation is deemed to be invalid, any more extensive interpretation, of which this is only a part, is likewise invalid, and further processing power need not be expended to check it. Thus, the inventive method is used to detect manufacturing defects by detecting paths that deviate from numerical acceptance norms for the periodic elements.
A symbolic designation is assigned to each run. In one embodiment of the invention, symbolic designations under dark runs, in the aperture mask inspection, include a sliver (SLIV), an entry vertical (NV), and an exit vertical (XV) and symbolic designations under light runs include xe2x80x9cLANDxe2x80x9d and xe2x80x9cHOLExe2x80x9d. SLIV is the designation used when the scan line passes through the dark sections on the top or bottom of a ring. Entry vertical is the designation used when the scan line passes through the dark section on the right of the center of the hole. Exit vertical is the designation used when the scan line passes through the dark section on the left of the center of the hole. HOLE is the designation used when the scan line passes through the light center of the hole and LAND is the designation used when the scan line passes through the light section outside of the hole. It should be noted that other designations may be made in other applications of the inventive system.
As would be apparent to those of ordinary skill in the art, rules used in the inventive method may be modified as long as there are enough defined rules to keep the systematic accounting of every possible interpretation from growing out of bounds and as long as the inspection problem is computable. That is, each path created from the systematic accounting of every possible interpretation in a scan line can be computed in the system, in parallel by multiple simple processors at very high speed.
It is therefore an object of the invention to provide a system and method for inspecting electronically acquired imagery by converting the image into an array of one-dimensional xe2x80x9cslicesxe2x80x9d of the target shape with every line the camera scans. The method includes means for breaking down each slice into segments, identifying every segment to determine what feature of the target shape the segment represents, sequencing each segment and using rules, to determine if each identified segment deviates from numerical acceptance norms for an annular element.
It is another object of the invention to provide a method for transforming a set of measurements that could be made on a two-dimensional image of the target area into a set of measurements made only on the one-dimensional data set.
It is another object of the invention to provide a method for using rules to analyze the periodic elements or arrays, whereby not all possibilities in the analysis work. The rules in the inventive method can be made to work even when the camera alignment is accidental.
It is another object of the invention to provide a system and method for producing integers from the reduction of the scan line data, whereby a collection of numbers each representing the brightness of a particular pixel results in xe2x80x9crun-length encodedxe2x80x9d data.
It is another object of the invention to provide a technique or search method for systematically accounting for every possible interpretation of each of the run-length integers and ignoring those interpretations that cannot be valid.
It is yet another object of the invention to provide a computational system and method for analyzing every possible interpretation of each of the run-length integers in parallel.
Additional features and advantages of the invention will be set forth in the description that follows, and in part will be apparent from the description, or may be learned by practice of the invention. The objectives and advantages of the invention will be realized and attained by the system particularly pointed out in the written description and claims hereof as well as the appended drawings.
To achieve these and other advantages and in accordance with the purpose of the invention, as embodied and broadly described, the present invention provides a method in a system for using electronically acquired imagery of an object to inspect the object for a wide variety of manufacturing defects, the method comprising the steps of: capturing, by a capturing means, an image of the object and converting the image into an array of periodic elements; delivering the array of periodic elements to a computer system for sequencing; reducing each periodic element into segments consisting of sets of similar adjacent pixels; systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of periodic elements; and systematically testing each interpretation wherein invalid interpretations are ignored.
The invention also provides a system for using electronically acquired imagery of an object to inspect the object for a wide variety of manufacturing defects, the system comprising: a capturing means for electronically capturing an image of the object and converting the image into an array of periodic elements; means for delivering the array of periodic elements from the capturing means to a computer system; and software means in the computer system for processing and reducing the array of periodic elements to a plurality of run-length integers whereby each run-length integer represents one run, systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of periodic elements, systematically testing each interpretation, and ignoring invalid interpretations.
The invention also provides a software component in a computer system for inspecting electronically acquired imagery of an object for a wide variety of manufacturing defects, the software component comprising: first processing mean for processing and reducing an array of periodic elements to a plurality of run-length integers whereby each run-length integer represents one run; second processing means for systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of periodic elements; and third processing means for systematically testing each interpretation and for ignoring invalid interpretations.
The invention also provides a system for using electronically acquired imagery of an object to inspect the object for a wide variety of manufacturing defects, the system comprising: a capturing means for electronically capturing an image of the object and converting the image into an array of periodic elements; means for delivering the array of periodic elements from the capturing means to a computer system; and software means in the computer system for processing and reducing the array of periodic elements to a plurality of run-length integers whereby each run-length integer represents one run, for systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of periodic elements, systematically testing each interpretation, and ignoring invalid interpretations; and a plurality of simple processors for parallel processing of a plurality of interpretations at very high speed.